#include <stack>
#include <vector>
#include <utility>
#include <iostream>

using namespace std;

namespace AlgoLib
{
	class SplayTree
	{
	private:
		static const int factor = 100;
		vector < int > leftSon, rightSon, par, key;
		stack < int > avail;
		int root;
		void init();
		int g(const int) const;
		void rotate(const int, const int = 0);
		int splay(const int);
		int	accessItem(const int, const int);
		int join(const int, const int);
		pair < int, int > split(const int, const int);
		int insertItem(const int, const int);
		int deleteItem(const int, const int);
		void private_debug(const int);

	public:
		SplayTree();
		~SplayTree();
		bool inTree(const int x)
		{
			if (root == 0)
			{
				return false;
			}
			return (key[root = accessItem(x, root)] == x);
		}

		void insert(const int x)
		{
			root = insertItem(x, root);
		}

		void erase(const int x)
		{
			root = deleteItem(x, root);
		}

		void debug();
	};

	SplayTree::SplayTree()
	{
		root = 0;
		init();
	}

	SplayTree::~SplayTree()
	{
	}

	void SplayTree::init()
	{
		leftSon.push_back(0);
		rightSon.push_back(0);
		par.push_back(0);
		key.push_back(0);
	}

	int SplayTree::g(const int x) const
	{
		return (par[par[x]]);
	}

	void SplayTree::rotate(const int y, const int dir)
	{
		// if dir == 0 then rotateLeft
		// if dir == 1 then rotateRight
		int x = rightSon[y], z = par[y];
		if (dir != 0)
		{
			x = leftSon[y];
		}
		if (z != 0)
		{
			if (leftSon[z] == y)
			{
				leftSon[z] = x;
			}
			else
			{
				rightSon[z] = x;
			}
		}
		if (dir == 0)
		{
			rightSon[y] = leftSon[x];
			leftSon[x] = y;
			if (rightSon[y] != 0)
			{
				par[rightSon[y]] = y;
			}
		}
		else
		{
			leftSon[y] = rightSon[x];
			rightSon[x] = y;
			if (leftSon[y] != 0)
			{
				par[leftSon[y]] = y;
			}
		}
		par[x] = z;
		par[y] = x;
	}

	int SplayTree::splay(const int x)
	{
		while (par[x] != 0)
		{
			if (x == leftSon[par[x]])
			{
				if (g(x) == 0)
				{
					rotate(par[x], 1);
				}
				else if (par[x] == leftSon[g(x)])
				{
					rotate(g(x), 1);
					rotate(par[x], 1);
				}
				else
				{ // par[x] == rightSon[g(x)]
					rotate(par[x], 1);
					rotate(par[x], 0);
				}
			}
			else
			{ // x == rightSon[par[x]]
				if (g(x) == 0)
				{
					rotate(par[x], 0);
				}
				else if (par[x] == rightSon[g(x)])
				{
					rotate(g(x), 0);
					rotate(par[x], 0);
				}
				else
				{ // par[x] == leftSon[g(x)]
					rotate(par[x], 0);
					rotate(par[x], 1);
				}
			}
		}
		return x;
	}
	
	int	SplayTree::accessItem(const int i, const int root)
	{
		int last(root);
		if (root == 0)
		{
			return root;
		}
		while (key[last] != i)
		{
			if (key[last] > i)
			{
				if (leftSon[last] != 0)
				{
					last = leftSon[last];
				}
				else
				{
					break;
				}
			}
			else
			{
				if (rightSon[last] != 0)
				{
					last = rightSon[last];
				}
				else
				{
					break;
				}
			}
		}
		return splay(last);
	}

	int SplayTree::join(const int t1, const int t2){
		if (t1 == 0)
		{
			return t2;
		}
		int last (t1);
		while (rightSon[last] != 0)
		{
			last = rightSon[last];
		}
		splay(last);
		if (t2 != 0)
		{
			par[t2] = last;
		}
		rightSon[last] = t2;
		return last;
	}

	pair < int, int > SplayTree::split(const int i, int root)
	{
		/* left tree will contain  *
		 * elements with the key   *
		 * not greater than i,     *
		 * right tree will contain *
		 * other elements          */
		int NewRoot = accessItem(i, root);
		int tree1, tree2;
		if (key[NewRoot] <= i)
		{
			tree2 = rightSon[NewRoot];
			rightSon[NewRoot] = 0;
			tree1 = NewRoot;
		}
		else
		{
			tree1 = leftSon[NewRoot];
			leftSon[NewRoot] = 0;
			tree2 = NewRoot;
		}
		return make_pair(tree1, tree2);
	}

	int SplayTree::insertItem(const int i, const int root)
	{
		int last(root), prev(root);
		while (last && key[last] != i)
		{
			prev = last;
			if (key[last] < i)
			{
				last = rightSon[last];
			}
			else
			{
				last = leftSon[last];
			}
		}
		if (last == 0)
		{
			if (avail.empty())
			{
				int size = key.size() - 1,
					p = size;
				size = (size != 0) ? ((size + 1) / 2) : factor;
				for (int i = 0; i < size; ++i)
				{
					init();
					avail.push(++p);
				}
			}
			last = avail.top();
			avail.pop();
			par[last] = prev;
			leftSon[last] = rightSon[last] = 0;
			key[last] = i;
			if (key[prev] < i)
			{
				rightSon[prev] = last;
			}
			else
			{
				leftSon[prev] = last;
			}
		}
		return splay(last);
	}

	int SplayTree::deleteItem(const int i, const int root)
	{
		int NewRoot = accessItem(i, root);
		if (key[NewRoot] == i)
		{
			avail.push(NewRoot);
			par[leftSon[NewRoot]] = par[rightSon[NewRoot]] = 0;
			return join(leftSon[NewRoot], rightSon[NewRoot]);
		}
		return NewRoot;
	}

	void SplayTree::private_debug(const int x)
	{
		if (x != 0)
		{
			private_debug(leftSon[x]);
			cerr << key[x] << endl;
			private_debug(rightSon[x]);
		}
	}

	void SplayTree::debug()
	{
		if (root == 0)
		{
			cerr << "empty tree" << endl;
		}
		else
		{
			private_debug(root);
		}
		cerr << endl;
	}
}
